{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Domino Rotations For Equal Row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDominoRotations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #行相等的最少多米诺旋转"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一排多米诺骨牌中，<code>tops[i]</code> 和 <code>bottoms[i]</code>&nbsp;分别代表第 <code>i</code> 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的&nbsp;—— 该平铺的每一半上都有一个数字。）</p>\n",
    "\n",
    "<p>我们可以旋转第&nbsp;<code>i</code>&nbsp;张多米诺，使得 <code>tops[i]</code> 和 <code>bottoms[i]</code>&nbsp;的值交换。</p>\n",
    "\n",
    "<p>返回能使 <code>tops</code> 中所有值或者 <code>bottoms</code> 中所有值都相同的最小旋转次数。</p>\n",
    "\n",
    "<p>如果无法做到，返回&nbsp;<code>-1</code>.</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/14/domino.png\" style=\"height: 300px; width: 421px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong> \n",
    "图一表示：在我们旋转之前， tops 和 bottoms 给出的多米诺牌。 \n",
    "如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。 \n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong> 在这种情况下，不可能旋转多米诺牌使一行的值相等。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= tops.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>bottoms.length == tops.length</code></li>\n",
    "\t<li><code>1 &lt;= tops[i], bottoms[i] &lt;= 6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-domino-rotations-for-equal-row](https://leetcode.cn/problems/minimum-domino-rotations-for-equal-row/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-domino-rotations-for-equal-row](https://leetcode.cn/problems/minimum-domino-rotations-for-equal-row/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,2,4,2,2]\\n[5,2,6,2,3,2]', '[3,5,1,2,3]\\n[3,6,3,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        x = 127\n",
    "        for i in range(len(tops)):\n",
    "            x &= (1<<tops[i])|(1<<bottoms[i])\n",
    "            if x == 0: return -1\n",
    "        x = bin((x&(-x))-1).count('1')\n",
    "        return len(tops) - max(tops.count(x), bottoms.count(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n",
    "        def get_min_cnt(key: int) -> int:\n",
    "            up = 0      #都放在上面行\n",
    "            down = 0    #都放在下面行\n",
    "            for x,y in zip(A, B):\n",
    "                if x != key and y != key:\n",
    "                    return float('inf')\n",
    "                elif x == key and y == key:\n",
    "                    continue\n",
    "                elif x == key and y != key:\n",
    "                    down += 1\n",
    "                else:\n",
    "                    up += 1\n",
    "            return min(up, down)\n",
    "\n",
    "        res1 = get_min_cnt(A[0])\n",
    "        res2 = get_min_cnt(B[0])\n",
    "        return -1 if (res1 == res2 == float('inf')) else min(res1, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        m1 = Counter(tops)\n",
    "        m2 = Counter(bottoms)\n",
    "        n = len(tops)\n",
    "        ans = inf\n",
    "        for k in m1.keys():\n",
    "            ok = True\n",
    "            for i in range(n):\n",
    "                if tops[i] != k and bottoms[i] != k:\n",
    "                    ok = False\n",
    "                    break\n",
    "            if ok:\n",
    "                print(k)\n",
    "                ans = min(ans, min(m1[k], n - m1[k]))\n",
    "        for k in m2.keys():\n",
    "            ok = True\n",
    "            for i in range(n):\n",
    "                if tops[i] != k and bottoms[i] != k:\n",
    "                    ok = False\n",
    "                    break\n",
    "            if ok:\n",
    "                print(k)\n",
    "                ans = min(ans, min(m2[k], n - m2[k]))\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        def check(x: int):\n",
    "            ra = rb = 0\n",
    "            for i in range(n):\n",
    "                if tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "                elif tops[i] != x:\n",
    "                    ra += 1\n",
    "                elif bottoms[i] != x:\n",
    "                    rb += 1\n",
    "            return min(ra, rb)\n",
    "\n",
    "        n = len(tops)\n",
    "        r = check(tops[0])\n",
    "        if r != -1 or tops[0] == bottoms[0]:\n",
    "            return r\n",
    "        else:\n",
    "            return check(bottoms[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        def check(x):\n",
    "            \"\"\"\n",
    "            Return min number of rotations \n",
    "            if one could make all elements in A or B equal to x.\n",
    "            Else return -1.\n",
    "            \"\"\"\n",
    "            # how many rotations should be done\n",
    "            # to have all elements in A equal to x\n",
    "            # and to have all elements in B equal to x\n",
    "            rotations_a = rotations_b = 0\n",
    "            for i in range(n):\n",
    "                # rotations coudn't be done\n",
    "                if tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "                # A[i] != x and B[i] == x\n",
    "                elif tops[i] != x:\n",
    "                    rotations_a += 1\n",
    "                # A[i] == x and B[i] != x\n",
    "                elif bottoms[i] != x:\n",
    "                    rotations_b += 1\n",
    "            # min number of rotations to have all\n",
    "            # elements equal to x in A or B\n",
    "            return min(rotations_a, rotations_b)\n",
    "\n",
    "        n = len(tops)\n",
    "        rotations = check(tops[0]) \n",
    "        # If one could make all elements in A or B equal to A[0]\n",
    "        if rotations != -1 or tops[0] == bottoms[0]:\n",
    "            return rotations \n",
    "        # If one could make all elements in A or B equal to B[0]\n",
    "        else:\n",
    "            return check(bottoms[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        same1 = tops[0]\n",
    "        same2 = bottoms[0]\n",
    "        for i in range(1,len(tops)):\n",
    "            if tops[i]==same1 or bottoms[i]==same1:\n",
    "                same1=same1\n",
    "            else:\n",
    "                same1 = -1 \n",
    "            if tops[i]==same2 or bottoms[i]==same2:\n",
    "                same2 = same2\n",
    "            else:\n",
    "                same2 = -1\n",
    "            if same1==-1 and same2==-1:\n",
    "                return -1\n",
    "        ts1 = 0\n",
    "        bs1 = 0\n",
    "        ts2 = 0\n",
    "        bs2 = 0\n",
    "        n = len(tops)\n",
    "        for i in range(len(tops)):\n",
    "            if tops[i] == same1:\n",
    "                ts1+=1\n",
    "            if bottoms[i]==same1:\n",
    "                bs1+=1\n",
    "            if tops[i]==same2 and same1!=same2:\n",
    "                ts2+=1\n",
    "            if bottoms[i] == same2 and same1!=same2:\n",
    "                bs2+=1\n",
    "        if ts2==0 and bs2==0:\n",
    "            return min(n-ts1,n-bs1)\n",
    "        else:\n",
    "            return min(n-ts1,n-bs1,n-ts2,n-bs2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        def check(x):\n",
    "            rotations_a = rotations_b = 0\n",
    "            for i in range(n):\n",
    "                if tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "                elif tops[i] != x:\n",
    "                    rotations_a += 1    \n",
    "                elif bottoms[i] != x:\n",
    "                    rotations_b += 1\n",
    "            return min(rotations_a, rotations_b)\n",
    "    \n",
    "        n = len(tops)\n",
    "        rotations = check(tops[0]) \n",
    "        if rotations != -1 or tops[0] == bottoms[0]:\n",
    "            return rotations \n",
    "        else:\n",
    "            return check(bottoms[0])\n",
    "\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:        \n",
    "    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n",
    "        def check(x):\n",
    "            \"\"\"\n",
    "            Return min number of swaps \n",
    "            if one could make all elements in A or B equal to x.\n",
    "            Else return -1.\n",
    "            \"\"\"\n",
    "            # how many rotations should be done\n",
    "            # to have all elements in A equal to x\n",
    "            # and to have all elements in B equal to x\n",
    "            rotations_a = rotations_b = 0\n",
    "            for i in range(n):\n",
    "                # rotations coudn't be done\n",
    "                if A[i] != x and B[i] != x:\n",
    "                    return -1\n",
    "                # A[i] != x and B[i] == x\n",
    "                elif A[i] != x:\n",
    "                    rotations_a += 1\n",
    "                # A[i] == x and B[i] != x    \n",
    "                elif B[i] != x:\n",
    "                    rotations_b += 1\n",
    "            # min number of rotations to have all\n",
    "            # elements equal to x in A or B\n",
    "            return min(rotations_a, rotations_b)\n",
    "    \n",
    "        n = len(A)\n",
    "        rotations = check(A[0]) \n",
    "        # If one could make all elements in A or B equal to A[0]\n",
    "        if rotations != -1 or A[0] == B[0]:\n",
    "            return rotations \n",
    "        # If one could make all elements in A or B equal to B[0]\n",
    "        else:\n",
    "            return check(B[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        c = Counter(chain(tops, bottoms))\n",
    "        n = len(tops)\n",
    "        l = c.most_common(2)\n",
    "        if len(l) == 1:\n",
    "            return 0\n",
    "        (first, cnt1), (second, cnt2) = l\n",
    "        if cnt1 < n:\n",
    "            return -1\n",
    "        if cnt1 == cnt2:\n",
    "            return -1 if any(t == b for t, b in zip(tops, bottoms)) else cnt1 >> 1\n",
    "        cnt = [n] * 2   # 上部分或下部分全部变为1需要的翻转数\n",
    "        for t, b in zip(tops, bottoms):\n",
    "            if first not in (t, b):\n",
    "                return -1\n",
    "            if t == first:\n",
    "                cnt[0] -= 1\n",
    "            if b == first:\n",
    "                cnt[1] -= 1\n",
    "        return min(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        tmp = (tops[0], bottoms[0])\n",
    "        for x in tmp:\n",
    "            if all(x in pair for pair in zip(tops, bottoms)):\n",
    "                return len(tops) - max(tops.count(x), bottoms.count(x))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        length = len(tops)\n",
    "        tops_count = Counter(tops)\n",
    "        bottoms_count = Counter(bottoms)\n",
    "        total_count = sorted(list((tops_count + bottoms_count).items()), key=lambda x: x[1], reverse=True)\n",
    "        top_change_times = 0\n",
    "        bottom_change_times = 0\n",
    "        min_change_times = float('inf')\n",
    "        for i in range(len(total_count)):\n",
    "            if total_count[i][1] < length:\n",
    "                break\n",
    "            for j in range(length):\n",
    "                if tops[j] != total_count[i][0] and bottoms[j] != total_count[i][0]:\n",
    "                    break\n",
    "                if tops[j] != total_count[i][0]:\n",
    "                    top_change_times += 1\n",
    "                elif bottoms[j] != total_count[i][0]:\n",
    "                    bottom_change_times += 1\n",
    "            else:\n",
    "                if min(top_change_times, bottom_change_times) < min_change_times:\n",
    "                    min_change_times = min(top_change_times, bottom_change_times)\n",
    "        return min_change_times if min_change_times != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        res=inf\n",
    "        for _ in range(1,7):\n",
    "            ans=0\n",
    "            for i in range(len(tops)):\n",
    "                if tops[i]==_: continue\n",
    "                if tops[i]!=_ and bottoms[i]==_: ans+=1\n",
    "                if tops[i]!=_ and bottoms[i]!=_: break\n",
    "            if i==len(tops)-1: res=min(res, ans)\n",
    "        for _ in range(1,7):\n",
    "            ans=0\n",
    "            for i in range(len(tops)):\n",
    "                if bottoms[i]==_: continue\n",
    "                if bottoms[i]!=_ and tops[i]==_: ans+=1\n",
    "                if bottoms[i]!=_ and tops[i]!=_: break\n",
    "            if i==len(tops)-1: res=min(res, ans)\n",
    "        return res if res!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        res=inf\n",
    "        for _ in range(1,7):\n",
    "            ans=0\n",
    "            for i in range(len(tops)):\n",
    "                if tops[i]==_: continue\n",
    "                if tops[i]!=_ and bottoms[i]==_:\n",
    "                    ans+=1\n",
    "                    if ans>res: break\n",
    "                if tops[i]!=_ and bottoms[i]!=_: break\n",
    "            if i==len(tops)-1: res=min(res, ans)\n",
    "        for _ in range(1,7):\n",
    "            ans=0\n",
    "            for i in range(len(tops)):\n",
    "                if bottoms[i]==_: continue\n",
    "                if bottoms[i]!=_ and tops[i]==_:\n",
    "                    ans+=1\n",
    "                    if ans>res: break\n",
    "                if bottoms[i]!=_ and tops[i]!=_: break\n",
    "            if i==len(tops)-1: res=min(res, ans)\n",
    "        return res if res!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        def check(x):\n",
    "            rotations_a = rotations_b = 0\n",
    "            for i in range(len(tops)):\n",
    "                if tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "                elif tops[i] != x:\n",
    "                    rotations_a += 1\n",
    "                elif bottoms[i] != x:\n",
    "                    rotations_b += 1\n",
    "            return min(rotations_a, rotations_b)\n",
    "        \n",
    "        rotations = check(tops[0])\n",
    "        if rotations != -1 or tops[0] == bottoms[0]:\n",
    "            return rotations\n",
    "        return check(bottoms[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        ans = inf\n",
    "        def cal(v):\n",
    "            u, d = 0, 0\n",
    "            for x, y in zip(tops, bottoms):\n",
    "                if x != v and y != v: return inf\n",
    "                elif x == v and y == v: continue\n",
    "                elif x != v and y == v: u += 1\n",
    "                else: d += 1\n",
    "            return min(u, d)\n",
    "        ans1 = cal(tops[0])\n",
    "        ans2 = cal(bottoms[0])\n",
    "        ans = min(ans1, ans2)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        avail = set()\n",
    "        avail.add(tops[0])\n",
    "        avail.add(bottoms[0])\n",
    "        n = len(tops)\n",
    "        for i in range(1, n):\n",
    "            if not tops[i] in avail and not bottoms[i] in avail:\n",
    "                return -1\n",
    "            else:\n",
    "                new_avail = set()\n",
    "                if tops[i] in avail:\n",
    "                    new_avail.add(tops[i])\n",
    "                if bottoms[i] in avail:\n",
    "                    new_avail.add(bottoms[i])\n",
    "                avail = new_avail\n",
    "        \n",
    "        if len(avail) == 1:\n",
    "            topcount, bottomcount = 0, 0\n",
    "            for i in range(n):\n",
    "                if tops[i] in avail and bottoms[i] in avail:\n",
    "                    continue\n",
    "                if tops[i] in avail:\n",
    "                    topcount += 1\n",
    "                if bottoms[i] in avail:\n",
    "                    bottomcount += 1\n",
    "            if topcount == n and bottomcount == n:\n",
    "                return 0\n",
    "            return min(topcount, bottomcount)\n",
    "            \n",
    "        elif len(avail) == 2:\n",
    "            tmp = avail.pop()\n",
    "            topcount, bottomcount = 0, 0\n",
    "            for i in range(n):\n",
    "                if tops[i] == bottoms[i] == tmp:\n",
    "                    continue\n",
    "                if tops[i] == tmp:\n",
    "                    topcount += 1\n",
    "                if bottoms[i] == tmp:\n",
    "                    bottomcount += 1\n",
    "            if topcount == n or bottomcount == n:\n",
    "                return 0\n",
    "            return min(topcount, bottomcount)\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:        \n",
    "    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n",
    "        def check(x):\n",
    "            \"\"\"\n",
    "            Return min number of swaps \n",
    "            if one could make all elements in A or B equal to x.\n",
    "            Else return -1.\n",
    "            \"\"\"\n",
    "            # how many rotations should be done\n",
    "            # to have all elements in A equal to x\n",
    "            # and to have all elements in B equal to x\n",
    "            rotations_a = rotations_b = 0\n",
    "            for i in range(n):\n",
    "                # rotations coudn't be done\n",
    "                if A[i] != x and B[i] != x:\n",
    "                    return -1\n",
    "                # A[i] != x and B[i] == x\n",
    "                elif A[i] != x:\n",
    "                    rotations_a += 1\n",
    "                # A[i] == x and B[i] != x    \n",
    "                elif B[i] != x:\n",
    "                    rotations_b += 1\n",
    "            # min number of rotations to have all\n",
    "            # elements equal to x in A or B\n",
    "            return min(rotations_a, rotations_b)\n",
    "    \n",
    "        n = len(A)\n",
    "        rotations = check(A[0]) \n",
    "        # If one could make all elements in A or B equal to A[0]\n",
    "        if rotations != -1 or A[0] == B[0]:\n",
    "            return rotations \n",
    "        # If one could make all elements in A or B equal to B[0]\n",
    "        else:\n",
    "            return check(B[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        res = -1\n",
    "        for num in range(1,7):\n",
    "            top_cot, bot_cot = 0,0\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if not (tops[i]==num or bottoms[i]==num):\n",
    "                    flag = False\n",
    "                    break\n",
    "                if tops[i]==num and bottoms[i]==num:\n",
    "                    pass\n",
    "                elif tops[i]==num:\n",
    "                    bot_cot += 1\n",
    "                else:\n",
    "                    top_cot += 1\n",
    "                pass\n",
    "            res = min(top_cot, bot_cot)\n",
    "            if flag:\n",
    "                return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        x, y = tops[0], bottoms[0]  # 答案只有可能在这两个中间\n",
    "        cnt_x = [n] * 2\n",
    "        cnt_y = [n] * 2\n",
    "        flag_x = flag_y = True  # 答案是否为a或b\n",
    "        for t, b in zip(tops, bottoms):\n",
    "            if flag_x:\n",
    "                if x not in (t, b):\n",
    "                    flag_x = False\n",
    "                if x == t:\n",
    "                    cnt_x[0] -= 1\n",
    "                if x == b:\n",
    "                    cnt_x[1] -= 1\n",
    "            if flag_y:\n",
    "                if y not in (t, b):\n",
    "                    flag_y = False\n",
    "                if y == t:\n",
    "                    cnt_y[0] -= 1\n",
    "                if y == b:\n",
    "                    cnt_y[1] -= 1\n",
    "            if not flag_x and not flag_y:\n",
    "                return -1\n",
    "        if flag_x:\n",
    "            return min(cnt_x)\n",
    "        return min(cnt_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        # 枚举1到6，对每个数字，分别计算让top全部为当前数字，以及让bottom全部为当前数字的操作次数\n",
    "        # 两者取较小值就行。如果找到一个数字可以让一行全部为它，直接返回答案就行\n",
    "        # 因为不可能存在另一个答案更小了。\n",
    "        n = len(tops)\n",
    "        res = -1\n",
    "        for num in range(1,7):\n",
    "            top_cot, bot_cot = 0,0\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if not (tops[i]==num or bottoms[i]==num):\n",
    "                    flag = False\n",
    "                    break\n",
    "                if tops[i]==num and bottoms[i]==num:\n",
    "                    pass\n",
    "                elif tops[i]==num:\n",
    "                    bot_cot += 1\n",
    "                else:\n",
    "                    top_cot += 1\n",
    "                pass\n",
    "            res = min(top_cot, bot_cot)\n",
    "            if flag:\n",
    "                return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:        \n",
    "    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n",
    "        def check(x):\n",
    "            \"\"\"\n",
    "            Return min number of swaps \n",
    "            if one could make all elements in A or B equal to x.\n",
    "            Else return -1.\n",
    "            \"\"\"\n",
    "            # how many rotations should be done\n",
    "            # to have all elements in A equal to x\n",
    "            # and to have all elements in B equal to x\n",
    "            rotations_a = rotations_b = 0\n",
    "            for i in range(n):\n",
    "                # rotations coudn't be done\n",
    "                if A[i] != x and B[i] != x:\n",
    "                    return -1\n",
    "                # A[i] != x and B[i] == x\n",
    "                elif A[i] != x:\n",
    "                    rotations_a += 1\n",
    "                # A[i] == x and B[i] != x    \n",
    "                elif B[i] != x:\n",
    "                    rotations_b += 1\n",
    "            # min number of rotations to have all\n",
    "            # elements equal to x in A or B\n",
    "            return min(rotations_a, rotations_b)\n",
    "    \n",
    "        n = len(A)\n",
    "        rotations = check(A[0]) \n",
    "        # If one could make all elements in A or B equal to A[0]\n",
    "        if rotations != -1 or A[0] == B[0]:\n",
    "            return rotations \n",
    "        # If one could make all elements in A or B equal to B[0]\n",
    "        else:\n",
    "            return check(B[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        same_counter = Counter()\n",
    "        top_counter  = Counter()\n",
    "        bottoms_counter = Counter()\n",
    "        for tv,bv in zip(tops,bottoms):\n",
    "            if tv == bv: same_counter[tv] += 1\n",
    "            top_counter[tv] += 1\n",
    "            bottoms_counter[bv] += 1\n",
    "        res = inf\n",
    "        tk,bk = top_counter.keys(),bottoms_counter.keys()\n",
    "        keys = set(tk) | set(bk)\n",
    "        \n",
    "        for k in keys:\n",
    "            if top_counter[k]+bottoms_counter[k]-same_counter[k] == n: \n",
    "                res = min(res,n-max(top_counter[k],bottoms_counter[k]))\n",
    "                \n",
    "        if  res == inf: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        def mlg(tops,bottoms,l):\n",
    "            n=len(tops)\n",
    "            t=0\n",
    "            b=0\n",
    "            for i in range(n):\n",
    "                if tops[i]!=l and bottoms[i]!=l:\n",
    "                    return -1\n",
    "                else:\n",
    "                    if tops[i]==l and bottoms[i]!=l:\n",
    "                        b+=1\n",
    "                    if bottoms[i]==l and tops[i]!=l:\n",
    "                        t+=1\n",
    "            return min(t,b)\n",
    "        a=tops[0]\n",
    "        b=bottoms[0]\n",
    "        m=mlg(tops,bottoms,a)\n",
    "        n=mlg(tops,bottoms,b)\n",
    "        if m>0 and n>0:\n",
    "            return min(m,n)\n",
    "        else:\n",
    "            return max(m,n)\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        if len(set(bottoms))==1 or len(set(tops))==1:return 0\n",
    "        from queue import PriorityQueue\n",
    "        from collections import Counter\n",
    "        n=len(tops)\n",
    "        mapping1=Counter(tops)\n",
    "        mapping2=Counter(bottoms)\n",
    "        queue=PriorityQueue()\n",
    "        for k,v in mapping1.items():\n",
    "            queue.put((-v,k))\n",
    "        for k,v in mapping2.items():\n",
    "            queue.put((-v,k))\n",
    "        while not queue.empty():\n",
    "            flag=False\n",
    "            cnt,dot=queue.get()\n",
    "            cnt=-cnt\n",
    "            if cnt<n//2:return -1\n",
    "            for i in range(n):\n",
    "                if tops[i]!=dot and bottoms[i]!=dot:\n",
    "                    flag=True\n",
    "                    break\n",
    "            if not flag:return n-cnt\n",
    "            '''if mapping1[dot]+mapping2[dot]>=n:\n",
    "                return n-cnt'''#判断能否做到，错误\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        if len(set(tops)) == 1 or len(set(bottoms)) == 1: return 0\n",
    "        ans = inf\n",
    "        for i in range(1, 7):\n",
    "            s = 0\n",
    "            for x, y in zip(tops, bottoms):\n",
    "                if x != i and y != i:\n",
    "                    break\n",
    "                if x != i and y == i:\n",
    "                    s += 1\n",
    "            else:\n",
    "                ans = min(ans, s)\n",
    "        \n",
    "        for i in range(1, 7):\n",
    "            s = 0\n",
    "            for x, y in zip(tops, bottoms):\n",
    "                if x != i and y != i:\n",
    "                    break\n",
    "                if y != i and x == i:\n",
    "                    s += 1\n",
    "            else:\n",
    "                ans = min(ans, s)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n",
    "        def get_min_cnt(key: int) -> int:\n",
    "            up = 0      #都放在上面行\n",
    "            down = 0    #都放在下面行\n",
    "            for x,y in zip(A, B):\n",
    "                if x != key and y != key:\n",
    "                    return float('inf')\n",
    "                elif x == key and y == key:\n",
    "                    continue\n",
    "                elif x == key and y != key:\n",
    "                    down += 1\n",
    "                else:\n",
    "                    up += 1\n",
    "            return min(up, down)\n",
    "\n",
    "        res1 = get_min_cnt(A[0])\n",
    "        res2 = get_min_cnt(B[0])\n",
    "        return -1 if (res1 == res2 == float('inf')) else min(res1, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        x, y = tops[0], bottoms[0]  # 答案只有可能在这两个中间\n",
    "        cnt_x = [n] * 2\n",
    "        cnt_y = [n] * 2\n",
    "        flag_x = flag_y = True  # 答案是否为a或b\n",
    "        for t, b in zip(tops, bottoms):\n",
    "            if flag_x:\n",
    "                if x not in (t, b):\n",
    "                    flag_x = False\n",
    "                if x == t:\n",
    "                    cnt_x[0] -= 1\n",
    "                if x == b:\n",
    "                    cnt_x[1] -= 1\n",
    "            if flag_y:\n",
    "                if y not in (t, b):\n",
    "                    flag_y = False\n",
    "                if y == t:\n",
    "                    cnt_y[0] -= 1\n",
    "                if y == b:\n",
    "                    cnt_y[1] -= 1\n",
    "            if not flag_x and not flag_y:\n",
    "                return -1\n",
    "        if flag_x:\n",
    "            return min(cnt_x)\n",
    "        return min(cnt_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        def check(x):\n",
    "            rotation_top = rotation_bottom = 0\n",
    "            for i in range(n):\n",
    "                if tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "                elif tops[i] != x:\n",
    "                    rotation_top += 1\n",
    "                elif bottoms[i] != x:\n",
    "                    rotation_bottom += 1\n",
    "            return min(rotation_bottom, rotation_top)\n",
    "            \n",
    "        rotations = check(tops[0])\n",
    "        if rotations != -1 or tops[0] == bottoms[0]:\n",
    "            return rotations\n",
    "        else:\n",
    "            return check(bottoms[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        same_counter = Counter()\n",
    "        top_counter  = Counter()\n",
    "        bottoms_counter = Counter()\n",
    "        for tv,bv in zip(tops,bottoms):\n",
    "            if tv == bv: same_counter[tv] += 1\n",
    "            top_counter[tv] += 1\n",
    "            bottoms_counter[bv] += 1\n",
    "        res = inf\n",
    "        keys = top_counter.keys() | bottoms_counter.keys()\n",
    "        for k in keys:\n",
    "            if top_counter[k]+bottoms_counter[k]-same_counter[k] == n: \n",
    "                res = min(res,n-max(top_counter[k],bottoms_counter[k]))\n",
    "                \n",
    "        if  res == inf: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        res = inf\n",
    "\n",
    "        for i in range(1, 7):\n",
    "            if tops.count(i) + bottoms.count(i) < len(tops):\n",
    "                continue\n",
    "            \n",
    "            count = 0\n",
    "            sumCount = 0\n",
    "\n",
    "            for j in range(n):\n",
    "                if tops[j] != i and bottoms[j] != i:\n",
    "                    count = -1\n",
    "                    break\n",
    "                elif tops[j] == i and tops[j] == bottoms[j]:\n",
    "                    continue\n",
    "                elif tops[j] == i and bottoms[j] != i:\n",
    "                    sumCount += 1\n",
    "                    continue\n",
    "                elif tops[j] != i and bottoms[j] == i:\n",
    "                    sumCount += 1\n",
    "                    count += 1\n",
    "            print(sumCount, count)\n",
    "\n",
    "            if count != -1:\n",
    "                res = min(count, sumCount - count, res)\n",
    "        \n",
    "        return -1 if res == inf else res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        tc, bc = [0] * 6, [0] * 6\n",
    "        n, vn = len(tops), len(tops)\n",
    "        candidate = -1\n",
    "        for i in range(n):\n",
    "            if tops[i] == bottoms[i]:\n",
    "                if candidate != -1 and candidate != tops[i]-1: return -1\n",
    "                candidate = tops[i] - 1 \n",
    "                vn -= 1\n",
    "            else:\n",
    "                tc[tops[i]-1] += 1\n",
    "                bc[bottoms[i]-1] += 1\n",
    "\n",
    "        if vn == 0:\n",
    "            return 0\n",
    "        \n",
    "        counter = [bc[i] + tc[i] for i in range(6)]\n",
    "        candidateCnt = max(counter) if candidate == -1 else counter[candidate]\n",
    "        \n",
    "        if candidateCnt < vn:\n",
    "            return -1\n",
    "        for i, v in enumerate(counter):\n",
    "            if v == candidateCnt:\n",
    "                candidate = i\n",
    "        return min(tc[candidate], bc[candidate])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        ans = inf\n",
    "        n = len(tops)\n",
    "        for x in range(1, 7):\n",
    "            cur = 0\n",
    "            for i in range(n):\n",
    "                if tops[i] == x:\n",
    "                    continue\n",
    "                elif bottoms[i] == x:\n",
    "                    cur += 1\n",
    "                else:\n",
    "                    cur = inf\n",
    "                    break\n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "        \n",
    "        for x in range(1, 7):\n",
    "            cur = 0\n",
    "            for i in range(n):\n",
    "                if bottoms[i] == x:\n",
    "                    continue\n",
    "                elif tops[i] == x:\n",
    "                    cur += 1\n",
    "                else:\n",
    "                    cur = inf\n",
    "                    break\n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "        \n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n",
    "        def get_min_cnt(key: int) -> int:\n",
    "            up = 0      #都放在上面行\n",
    "            down = 0    #都放在下面行\n",
    "            for x,y in zip(A, B):\n",
    "                if x != key and y != key:\n",
    "                    return float('inf')\n",
    "                elif x == key and y == key:\n",
    "                    continue\n",
    "                elif x == key and y != key:\n",
    "                    down += 1\n",
    "                else:\n",
    "                    up += 1\n",
    "            return min(up, down)\n",
    "\n",
    "        res1 = get_min_cnt(A[0])\n",
    "        res2 = get_min_cnt(B[0])\n",
    "        return -1 if (res1 == res2 == float('inf')) else min(res1, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        count_top = Counter(tops)\n",
    "        count_bottom = Counter(bottoms)\n",
    "        max_freq_top = 0\n",
    "        most_top = 0\n",
    "        most_bottom = 0\n",
    "        max_freq_bottom = 0\n",
    "\n",
    "        for i in range(len(tops)):\n",
    "            if count_top[tops[i]] > max_freq_top:\n",
    "                max_freq_top = count_top[tops[i]]\n",
    "                most_top = tops[i]\n",
    "            if count_bottom[bottoms[i]] > max_freq_bottom:\n",
    "                max_freq_bottom = count_bottom[bottoms[i]]\n",
    "                most_bottom = bottoms[i]\n",
    "        \n",
    "        rotate_top, rotate_bottom = 0, 0\n",
    "        for i in range(len(tops)):\n",
    "            if tops[i] != most_top:\n",
    "                if bottoms[i] == most_top:\n",
    "                    rotate_top += 1\n",
    "                else:\n",
    "                    rotate_top = -1\n",
    "                    break\n",
    "        for i in range(len(bottoms)):\n",
    "            if bottoms[i] != most_bottom:\n",
    "                if tops[i] == most_bottom:\n",
    "                    rotate_bottom += 1\n",
    "                else:\n",
    "                    rotate_bottom = -1\n",
    "                    break\n",
    "        \n",
    "        if rotate_top == rotate_bottom == -1:\n",
    "            return -1\n",
    "        elif rotate_top == -1:\n",
    "            return rotate_bottom\n",
    "        elif rotate_bottom == -1:\n",
    "            return rotate_top\n",
    "        else:\n",
    "            return min(rotate_top, rotate_bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        temp = [0, 0, 0, 0, 0, 0]\n",
    "        tar = 0\n",
    "        c = 0\n",
    "        max = 0\n",
    "\n",
    "        for i in tops:\n",
    "            temp[i - 1] = temp[i - 1] + 1\n",
    "        for i in bottoms:\n",
    "            temp[i - 1] = temp[i - 1] + 1\n",
    "        for i in range(6):\n",
    "            if temp[i] > max:\n",
    "                max = temp[i]\n",
    "        if max < len(tops):\n",
    "            return -1\n",
    "\n",
    "        for i in range(6):\n",
    "            if temp[i] >= len(tops):\n",
    "                tar = i + 1\n",
    "                break\n",
    "        for i in range(len(tops)):\n",
    "            if tops[i] != tar and bottoms[i] != tar:\n",
    "                return -1\n",
    "        t = 0\n",
    "        b = 0\n",
    "        for i in tops:\n",
    "            if i == tar:\n",
    "                t = t + 1\n",
    "        for i in bottoms:\n",
    "            if i == tar:\n",
    "                b = b + 1\n",
    "        if t >=b:\n",
    "            return len(tops) - t\n",
    "        else:\n",
    "            return len(tops) - b\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        c = collections.Counter(tops+bottoms)\n",
    "        ans1, ans2 = 0, 0\n",
    "        n = len(tops)\n",
    "        y = max(c.values())\n",
    "        if y >= n:\n",
    "            for x in c.keys():\n",
    "                if c[x] == y:\n",
    "                    break\n",
    "            for i in range(n):\n",
    "                if tops[i] != x and bottoms[i] == x:\n",
    "                    ans1 += 1\n",
    "                elif tops[i] == x and bottoms[i] != x:\n",
    "                    ans2 += 1\n",
    "                elif tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "            return min(ans1, ans2)\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        same_counter = Counter()\n",
    "        top_counter  = Counter()\n",
    "        bottoms_counter = Counter()\n",
    "        for tv,bv in zip(tops,bottoms):\n",
    "            if tv == bv: same_counter[tv] += 1\n",
    "            top_counter[tv] += 1\n",
    "            bottoms_counter[bv] += 1\n",
    "        res = inf\n",
    "        keys = top_counter.keys() | bottoms_counter.keys()\n",
    "        \n",
    "        for k in keys:\n",
    "            if top_counter[k]+bottoms_counter[k]-same_counter[k] == n: \n",
    "                res = min(res,n-max(top_counter[k],bottoms_counter[k]))\n",
    "                \n",
    "        if  res == inf: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        c = collections.Counter(tops+bottoms)\n",
    "        ans1, ans2 = 0, 0\n",
    "        n = len(tops)\n",
    "        y = max(c.values())\n",
    "        if y >= n:\n",
    "            for x in c.keys():\n",
    "                if c[x] == y:\n",
    "                    break\n",
    "            for i in range(n):\n",
    "                if tops[i] != x and bottoms[i] == x:\n",
    "                    ans1 += 1\n",
    "                elif tops[i] == x and bottoms[i] != x:\n",
    "                    ans2 += 1\n",
    "                elif tops[i] != x and bottoms[i] != x:\n",
    "                    return -1\n",
    "            return min(ans1, ans2)\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        if len(set(bottoms))==1 or len(set(tops))==1:return 0\n",
    "        from queue import PriorityQueue\n",
    "        from collections import Counter\n",
    "        n=len(tops)\n",
    "        mapping1=Counter(tops)\n",
    "        mapping2=Counter(bottoms)\n",
    "        queue=PriorityQueue()\n",
    "        for k,v in mapping1.items():\n",
    "            queue.put((-v,k))\n",
    "        for k,v in mapping2.items():\n",
    "            queue.put((-v,k))\n",
    "        while not queue.empty():\n",
    "            flag=False\n",
    "            cnt,dot=queue.get()\n",
    "            cnt=-cnt\n",
    "            for i in range(n):\n",
    "                if tops[i]!=dot and bottoms[i]!=dot:\n",
    "                    flag=True\n",
    "                    break\n",
    "            if not flag:return n-cnt\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "\n",
    "        # if can make one row into the same digit\n",
    "        # that number must be count more than len(tops)\n",
    "        # that makes it the most common number if we combine two list together\n",
    "        together = []\n",
    "        together.extend(tops)\n",
    "        together.extend(bottoms)\n",
    "        target = Counter(together).most_common(1)[0][0]\n",
    "\n",
    "        toT = toB = 0\n",
    "        for t, b in zip(tops, bottoms):\n",
    "            if t != target and b != target:\n",
    "                return -1\n",
    "            if t != target:\n",
    "                toT += 1\n",
    "            if b != target:\n",
    "                toB += 1\n",
    "        \n",
    "        return min(toT, toB)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        s = tops[:] + bottoms[:]\n",
    "        n = max(set(s), key=s.count)\n",
    "        top, bottom = 0, 0\n",
    "        for i, j in zip(tops, bottoms):\n",
    "            if i == n and j != n:\n",
    "                top += 1\n",
    "            elif i != n and j == n:\n",
    "                bottom += 1\n",
    "            elif i != n and j != n:\n",
    "                return -1\n",
    "        return min(top, bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        res = 1e9\n",
    "        n = len(tops)\n",
    "        rec = [[tops[i], bottoms[i]] for i in range(n)]\n",
    "        for r in [0, 1]:\n",
    "            for target in [1, 2, 3, 4, 5, 6]:\n",
    "                t = 0\n",
    "                flag = True\n",
    "                for i in range(n):\n",
    "                    if rec[i][r] == target:\n",
    "                        continue\n",
    "                    elif rec[i][1 - r] == target:\n",
    "                        t += 1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    res = min(res, t)\n",
    "        return res if res < 1e9 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        n = len(tops)\n",
    "        dp = [[0] * 7 for _ in range(n)]\n",
    "        temp = {tops[0], bottoms[0]}\n",
    "        for i in range(n):\n",
    "            temp &= {tops[i], bottoms[i]}\n",
    "            dp[0][tops[i]] += 1\n",
    "            dp[1][bottoms[i]] += 1\n",
    "        if not temp:\n",
    "            return -1\n",
    "        ans = n\n",
    "        for i in range(len(temp)):\n",
    "            val = temp.pop()\n",
    "            ans = min(ans, min(n - dp[0][val], n - dp[1][val]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        Top = {i: list(filter(lambda x: tops[x] == i, range(len(tops)))) for i in range(1, 7)}\n",
    "        Bom = {i: list(filter(lambda x: bottoms[x] == i, range(len(bottoms)))) for i in range(1, 7)}\n",
    "        ans = 0 \n",
    "        for i in range(1, 7):\n",
    "            if len(set(Top[i]+Bom[i])) == len(tops):\n",
    "                ans = max(max(len(Top[i]),len(Bom[i])), ans)\n",
    "        return len(tops)-ans if ans else -1\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:\n",
    "        Top = {i: list(filter(lambda x: tops[x] == i, range(len(tops)))) for i in range(1, 7)}\n",
    "        Bom = {i: list(filter(lambda x: bottoms[x] == i, range(len(bottoms)))) for i in range(1, 7)}\n",
    "        ans = 0 \n",
    "        for i in range(1, 7):\n",
    "            all = Top[i]+Bom[i]\n",
    "            if len(set(all)) == len(tops):\n",
    "                ans = max(max(len(Top[i]),len(Bom[i])), ans)\n",
    "        if ans == 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return len(tops)-ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
